package com.hans.exercise.sort;

/**
 * 归并排序 Created by Hans on 2014/4/11.
 */
public class JavaMergeSort {

  static Integer[] numbers = new Integer[]{7, 6, 3, 5, 4, 2, 4, 5, 10, 3, 1, 1};

  public static void merge(int l, int m, int r) {
    if (l == r) {
      return;
    }
    int[] t = new int[r - l + 1];
    int c = 0, j = m + 1, i = l;
    while (i <= m && j <= r) {
      if (numbers[i] < numbers[j]) {
        t[c++] = numbers[i++];
      } else {
        t[c++] = numbers[j++];
      }
    }
    while (i <= m) {
      t[c++] = numbers[i++];
    }
    while (j <= r) {
      t[c++] = numbers[j++];
    }
    for (c = 0; l <= r; ) {
      numbers[l++] = t[c++];
    }
  }

  public static void msSort(int l, int r) {
    if (l == r) {
      return;
    }
    int m = (l + r) / 2;
    msSort(l, m);
    msSort(m + 1, r);
    merge(l, m, r);
  }

  public static void main(String[] args) {
    msSort(0, numbers.length - 1);
    for (Integer number : numbers) {
      System.out.print(number + ",");
    }
  }
}
